package leetcode_core.leetcode_1;

public class UnionFind {
    //记录连通分量
    private int count;
    //数组定义:节点x的父亲节点是parent[x]
    private int[] parent;
    //新增一个数组记录树的重量
    private int[] size;

    public UnionFind(int n){
        //一开始各自不连通,那么就各自指向自己
        this.count = n;
        parent = new int[n];
        for(int i = 0;i<n;i++){
            parent[i] = i;
            size[i] = 1;//树的尺寸一开始都是1
        }
    }

    //将p节点和q节点进行链接
    public void union(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ){
            return ;
        }
        //小树接到大树下面,比较平衡
        if(size[rootP] > size[rootQ]){
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }else{
            parent[rootP] += rootQ;
            size[rootQ] += rootP;
        }
        this.count -- ;
    }
    //判断p和q是否连同
    public boolean isConnected(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
    //返回图中有几个连通分量
    public int count(){
        return count;
    }

    private int find(int x){//寻找根节点
        //根节点的parent[x] == x
        //这段代码的逻辑:x=parent[x],x赋值为其父节点的值
        //也就是向根节点逼近
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

}
